package com.heima.leetcode.datastructure.heap;

/**
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/6 15:54
 */
public class MaxHeap {
    private final int[] arr; // 当前包
    private int size;

    public MaxHeap(int capacity) {
        arr = new int[capacity];
    }

    public MaxHeap(int[] arr) {
        this.arr = arr;
        size = arr.length;
        heapify();
    }
    public boolean isFull(){
        return size == arr.length;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public boolean offer(int value){
        if (isFull()){
            return false;
        }
        up(size++,value);
        return true;
    }

    public int poll(){
        if (isEmpty()){
            throw new IllegalArgumentException("堆为空");
        }
        int value = arr[0];
        swap(0,--size);
        down(0);
        return value;
    }

    public int peek(){
        if (isEmpty()){
            throw new IllegalArgumentException("堆为空");
        }
        return arr[0];
    }

    public int size(){
        return size;
    }

    private void heapify(){
        for (int i = size / 2 - 1; i >= 0; i--){
            down(i);
        }
    }

    private void down(int parent){
        int leftChild = parent * 2 + 1;
        int rightChild = leftChild + 1;
        int max = maxValue(parent,leftChild,rightChild);
        if (max == parent){
            return;
        }
        swap(parent,max);
        down(max);
    }

    private void up(int index,int value){
        int child = index;
        int parent = (child - 1) / 2;
        while (child > 0 && arr[parent] < value){
            swap(parent,child);
            child = parent;
            parent = (child - 1) / 2;
        }
        arr[child] = value;
    }

    private int maxValue(int parent, int leftChild, int rightChild){
        if (leftChild >= size){
            return parent;
        }
        if (rightChild == size){
            return arr[parent] >= arr[leftChild] ? parent : leftChild; // 相等减少交换
        }
        if (arr[parent] >= arr[leftChild]){
            return arr[parent] >= arr[rightChild] ? parent : rightChild; // 相等减少交换
        }
        return arr[leftChild] >= arr[rightChild] ? leftChild : rightChild; // 相等走左边分支
    }

    private void swap(int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
